/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/remove-duplicates-from-sorted-array-ii
   @Language: C++
   @Datetime: 16-02-09 05:15
   */

// Method 1
class Solution {
public:
	/**
	 * @param A: a list of integers
	 * @return : return an integer
	 * Tips: Using two iterator left and right
	 *       Using c to record the num appear times
	 */
	int removeDuplicates(vector<int> &A) {
		// write your code here
		if (A.size() < 1) return 0;
		int c = 1;		// count current num appear times
		vector<int>::iterator l, r;
		for(r=A.begin(), l=r++; r!=A.end(); ++r){
			if (*r != *l){
				*(++l) = *r;
				c = 1;
			}
			else if(c == 1){
				*(++l) = *r;
				++c;
			}
		}
		A.erase(++l, r);
		return A.size();
	}
};

// Method 2
class Solution {
public:
	/**
	 * @param A: a list of integers
	 * @return : return an integer
	 */
	int removeDuplicates(vector<int> &nums) {
		// write your code here
		int len=0;
		for(int i=0, j=0; i<nums.size(); i=j){
			for(j=i+1; j<nums.size() && nums[i]==nums[j]; ++j);
			for(int k=0; k<2 && i+k<j; nums[len++]=nums[i+k++]);
		}
		return len;
	}
};

// Method 3
class Solution {
public:
	/**
	 * @param A: a list of integers
	 * @return : return an integer
	 */
	int removeDuplicates(vector<int> &nums) {
		// write your code here
		int len=0;
		for(int i=0; i<nums.size(); ++i)
			if(len<2||nums[i]!=nums[len-2]) nums[len++]=nums[i];
		return len;
	}
};
